package 蓝桥杯算法;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class day32 {
    public static void main(String[] args) {
        int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        //沉没孤岛
        int[][] arr={{1,1,0,0,0},{1,1,0,0,0},{0,0,1,0,0},{0,0,0,1,1}};
        for(int i=0;i<4;i++){
            if(arr[i][0]==1){
                bfs(arr,i,0);//把边上的全遍历一遍
            }
            if(arr[i][4]==1){
                bfs(arr,i,4);
            }
        }
        for(int j=0;j<5;j++){
            if(arr[0][j]==1){
                bfs(arr,0,j);
            }
            if(arr[3][j]==1){
                bfs(arr,3,j);
            }
        }
        for(int i=0;i<4;i++){
            for(int j=0;j<5;j++){
                if(arr[i][j]==1){
                    arr[i][j]=0;
                }
            }
        }
        for(int i=0;i<4;i++){
            for(int j=0;j<5;j++){
                if(arr[i][j]==2){
                    arr[i][j]=1;
                }
            }
        }
        for(int i=0;i<4;i++){
            for(int j=0;j<5;j++){
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
        //建造最大的岛屿
        int mark=2;
        Boolean[][] visited=new Boolean[4][5];
        for(int i=0;i<4;i++){
            for(int j=0;j<5;j++){
                visited[i][j]=false;
            }
        }
       int[][] graph={{1,1,0,0,0},{1,1,0,0,0},{0,0,1,0,0},{0,0,0,1,1}};
        HashMap<Integer,Integer> map=new HashMap<>();
        HashSet<Integer> set=new HashSet<>();
        int count=0;
        for(int i=0;i<4;i++){
            for(int j=0;j<5;j++){
                if(graph[i][j]==0){
                    visited[i][j]=false;
                }
                if(graph[i][j]==1){//指代没有标记的新的表
                    //记录最终的面积大小
                    count++;
                    dfs(graph,i,j,visited,count,mark);
                    //存储各个标记的大小
                    map.put(mark,count);
                    //把相应的值存入哈希表
                    mark++;

                }
            }
        }
        int result=0;
        for(int i=0;i<4;i++){
            for(int j=0;j<5;j++){
                if(graph[i][j]==0){
                    //清楚是为了方便下一次
                    set.clear();
                    int curSize=1;
                    for(int[] d:dir){
                       int x=i+d[0];
                       int y=j+d[1];
                       if(x<0||y<0||x>graph.length||y>graph[0].length){
                           continue;
                       }
                       //找到邻近的岛屿
                       int curMark=graph[i][j];
                       //如果已经弄过
                       if(set.contains(curMark)||!map.containsKey(curMark)){
                           continue;
                       }
                       //天上后变成的大小
                       curSize+=map.get(curMark);
                    }
                    result=Math.max(result,curSize);
                }
            }
        }
        System.out.println(result);
    }


    //建造最大的岛屿
    public static void dfs(int[][] graph, int x, int y, Boolean[][] visited,int count,int mark){
        if(x<0||x>=graph.length||y<0||y>=graph[0].length) {
            //终止条件
            return;
        }
        if(visited[x][y]||graph[x][y]==0){
            return;
        }
        visited[x][y]=true;
        count++;
        graph[x][y]=mark;//写上相应的标记
        //想起周围便利
        dfs(graph,x,y+1,visited,count,mark);
        dfs(graph,x,y-1,visited,count,mark);
        dfs(graph,x+1,y,visited,count,mark);
        dfs(graph,x-1,y,visited,count,mark);

    }
   public static void bfs(int[][] graph, int x, int y){
       int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; // 四个方向
       Queue<int[] > que=new LinkedList<>();
       que.add(new int[]{x,y});
       while(!que.isEmpty()){
           int[]cur=que.poll();
           int curx=cur[0];
           int cury=cur[1];
           for(int i=0;i<4;i++){
               int nex=curx+dir[i][0];
               int ney=cury+dir[i][1];
               if(nex<0||ney<0||nex>=graph.length||ney>=graph[0].length){
                  continue;
               }
               if(graph[nex][ney]==1){
                   que.add(new int[]{nex,ney});
                   //标记队列中改成2
                   graph[nex][ney]=2;
               }
           }
       }
   }
}
